from os import cpu_count

from Controller import Director
import Setting
from Setting import GridInfo
import math


class Classicmodel(Director):
    def __init__(self, set):
        super().__init__(set)
        self.next_click = set.first_click
        self.chance_calc = self.createCalc()
        self.wait_list = []
        self.check_list = []
        self.flag_list = []
        self.check2_list = []
        self.left_mine = self.set.mine_count

    def createCalc(self):
        """
        构造概率计算器
        :return:
        """
        x = self.set.height
        y = self.set.width
        mc = self.set.mine_count
        return ChanceCalculator(x, y, mc)

    def clearCheckList(self):
        self.check_list = []

    def clearFlagList(self):
        self.flag_list = []

    def setNextClick(self,x,y):
        """
        设置下一次点击的位置
        """
        self.next_click = (x, y)

    def getNextClick(self):
        """
         获取下次点击的位置
        :return:
        """
        return self.next_click

    def updateNextClick(self):
        (x,y) = self.wait_list.pop()
        self.setNextClick(x,y)

    def updateBoard(self,grid_list):
        for grid_row in grid_list:
            if grid_row.status != 0:
                self.check_list.append((grid_row.x,grid_row.y))
            self.chance_calc.setBoardCell(grid_row.x, grid_row.y, -1)

    def update(self,grid_list):
        """
        更新下次点击位置
        """

        # 初始化 概率版的flag，因为本次概率计算是否会出现爆雷概率为0的格子的情况未知
        self.chance_calc.init()

        # wait_list不为空，直接更新下次点击位置，不用进行策略分析
        if len(self.wait_list) > 0:
            # 更新下次点击位置
            print("本回合直接更新")
            self.updateNextClick()
            return []

        self.clearFlagList()

        # 扫描变化列表,取出数字格
        for grid_row in grid_list:
            if grid_row.status == 9:
                return [] # 可能可以优化
            elif grid_row.status > 0:
                self.check_list.append((grid_row.x, grid_row.y))

        # 先进行加减法简单策略,再根据等待队列长度是否为0，来判断是否执行复杂策略
        self.firstStrategy()
        if len(self.wait_list) > 0:
            print("本回合采用简单策略")
        else:
            # 执行第二步连通分量策略
            # 获取最小概略的格子列表, 如开头为0,则返回所有概略为0的格子位置的列表，否则，随机选取一个格子的位置
            print("本回合采用复杂策略")
            self.secondStrategy()

        # 更新下次点击位置
        self.updateNextClick()

        # self.left_mine -= len(self.flag_list)

        # 返回插旗列表(GridInfo 模式）
        return self.flag_list

    def firstStrategy(self):

        tmp_list = [] # 用于接收后续还会遍历到的格子

        # 第一步查周围未知格全是雷的格子
        # while len(self.check_list) > 0:
        #     (x,y) = self.check_list.pop()
        #     # todo
        #     self.checkAllMine(x,y)
        #     tmp_list.append((x,y))

        for x in range(self.set.height):
            for y in range(self.set.width):
                if self.reporter.isClicked(x,y) and self.monitor.getNum(x, y) > 0:
                 self.checkAllMine(x,y)
                 tmp_list.append((x,y))

        self.check_list = tmp_list
        tmp_list = []

        # 第二步查周围旗子数等于格子雷值，从而找出空白格
        while len(self.check_list) > 0:
            (x, y) = self.check_list.pop()
            # todo
            self.checkAround(x, y)
            tmp_list.append((x, y))

        self.check_list = tmp_list
        tmp_list = []

        #第三步检查两个带值格子的减法策略，找出雷格和空白格
        while len(self.check_list) > 0:
            (x, y) = self.check_list.pop()
            self.checkSub(x, y)
            tmp_list.append((x, y))

        # 简单策略到此结束，把剩余难以判断的格子放入复杂策略的等待格子
        self.check2_list = tmp_list
        self.check_list = tmp_list

    def checkAllMine(self, x, y):
        """
        检查一个格子是否值等于未知格数量, 或者雷数量已满，同时需要改掉reporter上的雷标记
        :param x:
        :param y:
        :return:
        """

        val = self.monitor.getNum(x,y)

        flags = self.reporter.unknownNum(x,y,val)

        if flags != [-1, -1]:
            for (x,y) in flags:
                self.flag_list.append(GridInfo(x, y, 11, True))
            return True

        return False

    def checkAround(self, x, y):
        val = self.monitor.getNum(x, y)

        blanks = self.reporter.blankNum(x, y, val)

        if blanks != [-1, -1]:
            self.wait_list.extend(blanks)
            return True

        return False

    def checkSub(self, x, y):
        val = self.monitor.getNum(x, y)

        if x < self.set.height - 1:
            val1 = self.monitor.getNum(x+1,y)
            if val1<8 and val1>0:
                (blanks, flags) = self.reporter.subNum(x,y,val,x+1,y,val1)
                for (x0, y0) in flags:
                    self.flag_list.append(GridInfo(x0, y0, 11, True))
                self.wait_list.extend(blanks)

        if y < self.set.width - 1:
            val2 = self.monitor.getNum(x,y+1)
            if val2<8 and val2>0:
                (blanks, flags) = self.reporter.subNum(x,y,val,x,y+1,val2)
                for (x0, y0) in flags:
                    self.flag_list.append(GridInfo(x0, y0, 11, True))
                self.wait_list.extend(blanks)

    def secondStrategy(self):
        """

        :return:
        """
        self.left_mine = self.calcMineLeft()
        cc_list, cc_graph = self.findAllList()
        print(cc_list)
        print(cc_graph)
        print(self.left_mine)
        self.reporter.printBoard()
        self.monitor.printBoard()
        cc_perm_list = []

        for cc in cc_list:
            perm = dict()
            self.backtrace_cc(self.reporter.getBoard(),cc,perm,0,0)
            cc_perm_list.append(perm)

        avg_cc_minecnt = self.calc_cc_points(cc_list,cc_perm_list)

        if self.chance_calc.checkZero():
            self.wait_list.extend(self.chance_calc.getMinChance())
            return

        isolated_cell_num = self.set.width * self.set.height - self.referee.count
        for cc in cc_list:
            isolated_cell_num -= len(cc)

        if isolated_cell_num > 0:
            isolated_cell_prob = round((self.left_mine - avg_cc_minecnt) / isolated_cell_num, 6)
            if abs(isolated_cell_prob) < 1e-5:
                isolated_cell_prob = 0
            for i in range(len(cc_graph)):
                for j in range(len(cc_graph[0])):
                    if cc_graph[i][j] == -1 and self.reporter.isClickable(i,j):
                        self.chance_calc.setBoardCell(i,j,isolated_cell_prob)
                    elif self.reporter.isFlag(i,j):
                        self.chance_calc.setBoardCell(i, j, 1)

        if self.chance_calc.checkZero():
            self.wait_list.extend(self.chance_calc.getMinChance())
            return

        if len(self.wait_list) == 0:
            prepare_list = self.chance_calc.getMinChance()
            x_max = self.set.height - 1
            y_max = self.set.width - 1
            for x, y in prepare_list:
                if x==0 or x==x_max or y==0 or y==y_max:
                    self.wait_list.append((x,y))
                    return

            self.wait_list.append(prepare_list[0])

    def calcMineLeft(self):
        res = self.set.mine_count
        for x in range(self.set.height):
            for y in range(self.set.width):
                if self.reporter.isFlag(x,y):
                    res -= 1
        return res

    def findAllList(self):
        """
        找出所有联通分量
        :return:
        """
        board = self.chance_calc.createBoard(-1) # 复用一下这个函数，实际用来记录格子是否访问过 -1代表未访问
        cc_list = []
        height = self.set.height
        width = self.set.width
        new_cc_flag = False
        id = 1

        for (x,y) in self.check2_list:
            if board[x][y] == -1:
                tmp = []
                queue = [(x,y)]
                while len(queue) > 0:
                    x0, y0 = queue.pop()
                    board[x0][y0] = 0

                    for i in range(max(0, x0 - 1), min(x0 + 2, height)):
                        for j in range(max(0, y0 - 1), min(y0 + 2, width)):
                            if board[i][j] == -1 and self.reporter.isClickable(i, j):
                                board[i][j] = id
                                tmp.append((i,j))
                                new_cc_flag = True

                                for i0 in range(max(0, i - 1), min(i + 2, height)):
                                    for j0 in range(max(0, j - 1), min(j + 2, width)):
                                        if board[i0][j0] == -1 and self.reporter.isClicked(i0,j0):
                                            queue.append((i0,j0))


                if new_cc_flag:
                    new_cc_flag = False
                    id += 1
                    cc_list.append(tmp)

        return cc_list, board

    def backtrace_cc(self, board, cc, cc_perm, index, i_mine):
        """
        回溯法找出每一个连通分量的总排列组合，以及每个格子在所有可能组合的雷数
        :param board:
        :param cc:
        :param cc_perm:
        :param index:
        :param i_mine:
        :return:
        """

        if index>=len(cc):
            count = [] # 前len(cc)位保存每个点有多少种组合里面出现过雷
            flag = False
            l = len(cc)

            if i_mine in cc_perm.keys():
                count = cc_perm[i_mine]
            else:
                for i in range(0, l+1):
                    count.append(0)
                flag =True

            for i in range(0, l):
                (x, y) = cc[i]
                if board[x][y]==-1:
                    count[i] += 1

            count[l] += 1

            if flag:
                cc_perm[i_mine] = count

            return 1

        all_P = 0
        (x, y) = cc[index]
        board[x][y] = -1
        if i_mine < self.left_mine and self.isLegal(board,x,y):
            all_P += self.backtrace_cc(board[:],cc,cc_perm,index+1,i_mine+1)

        board[x][y] = 0
        if self.isLegal(board,x,y):
            all_P += self.backtrace_cc(board[:], cc, cc_perm, index + 1, i_mine)

        return all_P

    def isLegal(self, board, x, y):
        """
        回溯法中检查一个未点击格子周围是否合法
        :param board:
        :param x:
        :param y:
        :return:
        """
        queue = []

        for i in range(max(0, x - 1), min(x + 2, self.set.height)):
            for j in range(max(0, y - 1), min(y + 2, self.set.width)):
                if board[i][j] == 1:
                    queue.append((i,j))

        while len(queue) > 0:
            (x0, y0) = queue.pop()
            flag = 0
            clickable = 0
            for i in range(max(0, x0 - 1), min(x0 + 2, self.set.height)):
                for j in range(max(0, y0 - 1), min(y0 + 2, self.set.width)):
                    if board[i][j] == 0:
                        clickable += 1
                    elif board[i][j] == -1:
                        flag += 1
            num = self.monitor.getNum(x0, y0)
            if flag > num or flag + clickable < num:
                return False

        return True

    def calc_cc_points(self, cc_list, cc_perm_list):
        maxn_mine = self.left_mine
        minn_mine = self.set.width * self.set.height - self.referee.count
        for cc in cc_list:
            minn_mine -= len(cc)
        not_in_cc =minn_mine
        minn_mine = maxn_mine - not_in_cc
        avg = 0

        queue = []
        head = dict()
        head[0] = 1
        queue.append(head)

        for perm in cc_perm_list:
            pre = queue[len(queue) - 1]
            cur = self.merge_perms(pre, perm, maxn_mine, True)
            queue.append(cur)

        all_perm_num = 0
        top = queue.pop()

        print(cc_perm_list)
        print(queue)
        print(top)
        for k, v in top.items():
            m = maxn_mine - k
            if m<0 or m > not_in_cc:
                print(f"not in cc {not_in_cc}; mine {m}")
                continue
            all_perm_num += v * math.comb(not_in_cc, m)

        print(f"all_perm_num {all_perm_num}")

        right = head
        i = len(cc_list) - 1

        while i>=0:
            cc = cc_list[i]
            cc_perm = cc_perm_list[i]

            left = queue.pop()
            except_i_perms = self.merge_perms(left, right, maxn_mine, False)
            right = self.merge_perms(except_i_perms, cc_perm, maxn_mine, True)

            for k1, v1 in cc_perm.items():
                cell_perm = 0
                for k2, v2 in except_i_perms.items():
                    mine_num = k1+k2
                    if mine_num < minn_mine or mine_num >maxn_mine:
                        continue
                    cell_perm +=  v2 * math.comb(not_in_cc, maxn_mine - mine_num)

                for j in range(len(cc)):
                    x, y = cc[j]
                    if (v1[j] == 0 or cell_perm == 0) and all_perm_num == 0:
                        prob = 0
                    else:
                        prob = round(v1[j] * cell_perm / all_perm_num, 6)
                    self.chance_calc.setBoardCell(x, y, prob)
                    avg += prob

            i -= 1

        return avg

    def merge_perms(self, perm1, perm2, maxn_mine, flag):
        """
        综合考虑两个连通分量之间，在不同雷数下，有多少种排列
        :param perm1:
        :param perm2:
        :param maxn_mine:
        :param flag:
        :return:
        """

        res = dict()

        for k1,v1 in perm1.items():
            for k2,v2 in perm2.items():
                new_k = k1 + k2
                new_v = v1

                if new_k > maxn_mine:
                    continue
                if flag:
                    new_v *= v2[len(v2) - 1]
                else:
                    new_v *= v2

                if new_k in res:
                    new_v += res[new_k]
                    res[new_k] = new_v
                else:
                    res[new_k] = new_v

        return res



class ChanceCalculator:
    def __init__(self,x,y,mine_count):
        self.x=x
        self.y=y
        self.mine_count = mine_count
        self.board = self.createBoard() # 2 未计算; -1 揭示格  1 雷格; -2 失败计算
        self.zero_check = False
        self.min_chance = 2
        self.cell_list = []

    def createBoard(self, val = 2):
        ans = []
        for i in range(self.x):
            ans.append([])
            for j in range(self.y):
                ans[i].append(val)

        return ans

    def init(self):
        self.zero_check = False
        self.min_chance = 2
        self.cell_list = []

    def checkZero(self):
        return self.zero_check

    def setBoardCell(self, x, y, val):
        self.board[x][y] = val
        if abs(val) < 1e-5:
            self.zero_check = True
            if self.min_chance != 0:
                self.min_chance = 0
                self.cell_list = [(x,y)]
            else:
                self.cell_list.append((x,y))
        else:
            self.updateMin(x,y,val)

    def updateMin(self, x, y, val):
        if val < self.min_chance:
            self.min_chance = val
            self.cell_list = [(x,y)]
        elif abs(val - self.min_chance) < 1e-5:
            self.cell_list.append((x, y))


    def getBoardCell(self, x, y):
        return self.board[x][y]

    def getMinChance(self):
        """
        获取最小概略的格子列表
        :return:
        """
        return self.cell_list

